package simple.linklist;

import struct.ListNode;

/**
 * <a href="https://leetcode-cn.com/problems/merge-two-sorted-lists">21. 合并两个有序链表</a>
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * 示例 1：
 *   输入：l1 = [1,2,4], l2 = [1,3,4]
 *   输出：[1,1,2,3,4,4]
 * 示例 2：
 *   输入：l1 = [], l2 = []
 *   输出：[]
 * 示例 3：
 *   输入：l1 = [], l2 = [0]
 *   输出：[0]
 * 提示：
 *   两个链表的节点数目范围是 [0, 50]
 *   -100 <= Node.val <= 100
 *   l1 和 l2 均按 非递减顺序 排列
 * 解题思路：
 *   1.定义一个初始化头结点，以及一个尾节点，尾节点初始指向头结点
 *   2.当节点1小于节点2时，尾节点的next指向节点1，节点1往后移
 *   3.当节点1大于等于节点2时，尾节点的next指向节点2，节点2往后移
 *   4.更新尾节点为下一节点
 *   5.当节点1或节点2为null时，表示其中一个链表移到结尾了，可将尾节点的next直接指向另一个节点，表示拼接剩余节点
 *   6.返回头结点的下一个节点，即拼接后的链表头结点
 * @author 刘学松
 * @date 2021-03-16 11:06
 */
public class 合并两个有序链表 {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode();
        ListNode tail = head;
        while (true) {
            if (l1 == null) {
                tail.next = l2;
                break;
            }
            if (l2 == null) {
                tail.next = l1;
                break;
            }
            if (l1.val < l2.val) {
                tail.next = l1;
                l1 = l1.next;
            } else {
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;
        }
        return head.next;
    }
}
